class Node{
public:
    int key;
    int val;
    Node* next;
    Node* prev;
    Node(int k=0,int v=0):key(k),val(v){}
};

class LRUCache {
private:
    int capacity;
    Node* newhead;
    unordered_map<int,Node*>m;
public:
    LRUCache(int capacity):capacity(capacity),newhead(new Node()) {
        newhead->next=newhead;
        newhead->prev=newhead;
    }
    void remove(Node* x){
        x->next->prev=x->prev;
        x->prev->next=x->next;
    }
    void push_front(Node*x){
        x->next=newhead->next;
        newhead->next=x;
        x->next->prev=x;
        x->prev=newhead;
    }
    Node* get_node(int key){
        auto it=m.find(key);
        if(it==NULL)
            return NULL;
        auto node=it->second;
        remove(node);
        push_front(node);
        return node;
    }
    int get(int key) {
        auto node=get_node(key);
        return node?node->val:-1;
    }
    
    void put(int key, int value) {
        auto node=get_node(key);
        if(node!=NULL)
        {
            node->val=value;
            return ;
        }
        node=new Node(key,value);
        push_front(node);
        m[key]=node;
        if(m.size()>capacity){
            auto back_node=newhead->prev;
            remove(back_node);
            m.erase(back_node->key);
            delete back_node;
        }
    }
};